package com.leetcode.根据算法进行分类.滑动窗口相关;


import java.util.LinkedList;
import java.util.Queue;

/**
 * @author: ZhouBert
 * @date: 2021/2/18
 * @description: 995. K 连续位的最小翻转次数
 * https://leetcode-cn.com/problems/minimum-number-of-k-consecutive-bit-flips/
 * 新思想：差分数组 + 前缀和数组（by the way）
 * 由于队列实在是太难想到了！所以这里有参考：
 * https://blog.csdn.net/qq_17550379/article/details/87685137
 * 如果队列想通了以后，差分数组应该就好代入了
 * https://blog.csdn.net/qq_21201267/article/details/110858906
 * --
 * 强化题目：
 * 1094. 拼车
 * 370. 区间加法（差分思想）
 * 732. 我的日程安排表 III（差分思想）
 * 1674. 使数组互补的最少操作次数（差分思想）
 */
public class C_995_K连续位的最小翻转次数 {

	public static void main(String[] args) {
		C_995_K连续位的最小翻转次数 action = new C_995_K连续位的最小翻转次数();
		test1(action);
//		test2(action);
//		test3(action);
	}


	public static void test1(C_995_K连续位的最小翻转次数 action) {
		// 3
		int[] A = new int[]{0, 0, 0, 1, 0, 1, 1, 0};
		int k = 3;
//		int res = action.minKBitFlipsFaster(A, k);
		//int res = action.minKBitFlipsByDifferentialArray(A, k);
		int res = action.minKBitFlipsByQueue(A, k);

		System.out.println("res = " + res);
	}

	public static void test2(C_995_K连续位的最小翻转次数 action) {
		// 1
		int[] A = new int[]{0, 1, 0};
		int k = 1;
		int res = action.minKBitFlipsFaster(A, k);
		System.out.println("res = " + res);
	}

	public static void test3(C_995_K连续位的最小翻转次数 action) {
		// 1
		int[] A = new int[]{1, 1, 0};
		int k = 2;
		int res = action.minKBitFlipsFaster(A, k);
		System.out.println("res = " + res);
	}

	/**
	 * 本来想着用贪心，但是又怕考虑不周全；
	 * 但是题目提醒的是贪心，同时又木有其他的办法，只能先试一下了。
	 * --
	 * 从左往右翻
	 * 居然超时了
	 * --
	 * 考虑优化：
	 * 1.使用异或进行优化
	 *
	 * @param A
	 * @param K
	 * @return
	 */
	public int minKBitFlips(int[] A, int K) {
		int begin = 0, end = K, nextBegin = 0;
		int len = A.length;
		//标志位用来判断反转中第一个为 0 的
		boolean flag = false;
		//翻转次数
		int res = 0;
		while (end <= len) {
			if (A[begin] == 0) {
				A[begin] = 1;
				for (int i = begin + 1; i < end; i++) {
					if (A[i] == 0) {
						A[i] = 1;
					} else {
						A[i] = 0;
						if (!flag) {
							nextBegin = i;
							flag = true;
						}
					}
				}
				if (begin == nextBegin) {
					//说明窗口中都为 1
					begin = end;
				} else {
					begin = nextBegin;
				}
				end = begin + K;
				res++;
				flag = false;
			} else {
				begin++;
				end++;
			}
		}
		//从 begin 开始检测
		for (int i = begin; i < len; i++) {
			if (A[i] == 0) {
				return -1;
			}
		}
		return res;
	}

	/**
	 * 使用【异或】可以通过！
	 * 看来用 nextBegin 进行优化的意义不大阿！！！
	 *
	 * @param A
	 * @param K
	 * @return
	 */
	public int minKBitFlipsFaster(int[] A, int K) {
		int begin = 0, end = K;
		int len = A.length;
		//翻转次数
		int res = 0;
		while (end <= len) {
			if (A[begin] == 0) {
				for (int i = begin; i < end; i++) {
					A[i] ^= 1;
				}
				res++;
			}
			begin++;
			end++;
		}
		//从 begin 开始检测
		for (int i = begin; i < len; i++) {
			if (A[i] == 0) {
				return -1;
			}
		}
		return res;
	}

	/**
	 * 通过差分数组实现
	 * 啊差分数组太难理解了
	 *
	 * @param A
	 * @param K
	 * @return
	 */
	public int minKBitFlipsByDifferentialArray(int[] A, int K) {
		int n = A.length;
		//diff[i] =A[i-1]-A[i]
		int[] diff = new int[n + 1];
		int ans = 0, revCnt = 0;
		for (int i = 0; i < n; ++i) {
			revCnt += diff[i];
			if ((A[i] + revCnt) % 2 == 0) {
				if (i + K > n) {
					return -1;
				}
				++ans;
				++revCnt;
				--diff[i + K];
			}
		}
		return ans;
	}

	/**
	 * 通过 队列来实现
	 * TODO: 如果只是从题解里的结果出发，很难理解；但是如果理解了思想，就会更容易往结果接近！
	 * 优化的方向为：
	 * 将反转记录存储，直到最后再进行反转
	 * --
	 * 看来思想还不对，这种记录的方式依然需要 O(n)
	 * --
	 * 那么接下来优化的方向就是：
	 * 如何使用 O(1) 的优化呢
	 *
	 * @param A
	 * @param K
	 * @return
	 */
	public int minKBitFlipsByRecord(int[] A, int K) {
		int len = A.length;
		//记录
		int[] r = new int[len];
		int res = 0;
		for (int i = 0; i < len; i++) {
			//(r[i]&1) 如果余数为 0 --> 根据以往的记录说明不需要反转
			//但是真正反转与否取决于 最后的值
			if ((((r[i] & 1) == 0) ? A[i] : A[i] ^ 1) == 0) {
				if (i + K > len) {
					//如果此时还发现 0 的元素存在
					return -1;
				}

				//如果最后的结果 == 0
				//说明还需要 反转
				for (int j = i + 1; j < i + K; j++) {
					r[j]++;
				}
				res++;
			}
		}
		return res;
	}

	/**
	 * 通过一个队列来辅助记录反转
	 * queue 记录每一次反转的索引；
	 * 关键：可以通过 A[i] + queue.size() 是否为偶数来判断当前位置是否需要反转！！！
	 * 卧槽，感觉这个观察太仔细了！
	 * 当队头元素超过限制时，此时对头元素没有后续判断意义，就可以移除了。
	 * @param A
	 * @param K
	 * @return
	 */
	public int minKBitFlipsByQueue(int[] A, int K) {
		int len = A.length;
		//记录
		Queue<Integer> queue = new LinkedList<>();
		int res = 0;
		for (int i = 0; i < len; i++) {
			while (!queue.isEmpty() && queue.peek() == i - K) {
				queue.poll();
			}
			if (((A[i] + queue.size()) & 1) == 0) {
				if (i + K > len) {
					//如果此时还发现 0 的元素存在
					return -1;
				}
				queue.offer(i);
				res++;
			}

		}
		return res;
	}


}
